import java.util.*;

public class Test_8_31 {


    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode() {
        }

        public TreeNode(int val) {
            this.val = val;
        }
    }


    //力扣：100. 相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;

        //1. 判断两棵树根结点的值是否相同
        if(p.val == q.val) {
            //2.判断两棵树的左子树是否相同
            boolean leftRet = isSameTree(p.left, q.left);
            if(!leftRet) return false;
            //3. 判断两棵树的右子树是否相同
            boolean rightRet = isSameTree(p.right, q.right);
            if(!rightRet) return false;

            return true;
        }else {
            return false;
        }
    }





    //力扣：572. 另一棵树的子树
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //1. 判断root 与 subRoot 是否是相同（包含两者都为空树的情况）
        if(isSameTree(root, subRoot)) return true;

        //2. 如果root 为空，则不能进行以下判断，且subRoot 一定不为 root的子树
        if(root == null) return false;

        //3. 判断root.left 和 root.right 是否与subRoot 相同
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);

    }
//    public boolean isSameTree(TreeNode p, TreeNode q) {
//        if(p == null && q == null) return true;
//        if(p == null || q == null) return false;
//
//        //1. 判断两棵树根结点的值是否相同
//        if(p.val != q.val) {
//            //2.判断两棵树的左子树和右子树是否相同
//            return false;
//        }else {
//            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
//        }
//    }



    //力扣：226. 翻转二叉树
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;

        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        root.left = invertTree(root.left);
        root.right = invertTree(root.right);

        return root;
    }




    //牛客网：KY11 二叉树遍历
    //根据给出的前序遍历结果，构建二叉树，并输出中序遍历的结果
    static int i;
//    public static void main(String[] args) {
//        Scanner in = new Scanner(System.in);
//        // 注意 hasNext 和 hasNextLine 的区别
//        while (in.hasNextLine()) { // 注意 while 处理多个 case
//            String str = in.nextLine();
//            Test_8_31.i = 0;
//            TreeNode root = createTree(str);
//            inOrder(root);
//            System.out.println();
//        }
//    }
//    public static TreeNode createTree(String str) {
//
//        TreeNode root = new TreeNode();
//        if(str.charAt(i) != '#') {
//            root.val = str.charAt(i);
//            i++;
//            root.left = createTree(str);
//            root.right = createTree(str);
//        }else {
//            root = null;
//            i++;
//        }
//        return root;
//    }
    public static void inOrder(TreeNode root) {
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }



    //力扣：102. 二叉树的层序遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) return ret;

        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int sz = q.size();

            while(sz > 0) {
                TreeNode tmp = q.poll();
                list.add(tmp.val);
                if(tmp.left != null) q.offer(tmp.left);
                if(tmp.right != null) q.offer(tmp.right);
                sz--;
            }
            ret.add(list);
        }
        return ret;
    }



    //力扣：105. 从前序与中序遍历序列构造二叉树
    private int preIndex;       //每个前序遍历序列中的根结点的下标
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder, inorder, 0, preorder.length-1);
    }
    private TreeNode buildTreeChild(int[] preorder, int[] inorder, int inbegin, int inend) {
        //1. 构建当前 树 的根结点
        if(inbegin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);

        //2. 找到 根结点 在中序遍历序列 中的下标
        int rootIndex = getIndex(inorder,inbegin,inend, preorder[preIndex]);
        preIndex++;

        //3. 构建根结点的 左子树 和 右子树
        root.left = buildTreeChild(preorder, inorder, inbegin, rootIndex-1);
        root.right = buildTreeChild(preorder, inorder, rootIndex+1, inend);

        return root;
    }
    private int getIndex(int[] inorder, int inbegin, int inend, int key) {
        for(int i = inbegin; i <= inend; i++) {
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }




}
